package com.chj.dfs.class04;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Code17_WordLadder {
	// 计算两个单词之间不相等的字符个数
	public static boolean connect(String word1, String word2) {
		int cnt = 0;
		for (int i = 0; i < word1.length(); i++) {
			if (word1.charAt(i) != word2.charAt(i)) {
				cnt++;
			}
		}
		// 若两个单词之间只有一个字符不同，则返回true
		return cnt == 1;
	}

	public static void construct_graph(String beginWord, List<String> wordList, Map<String, List<String>> graph) {
		wordList.add(beginWord);
		for (int i = 0; i < wordList.size(); i++) {
			graph.put(wordList.get(i), new ArrayList<>());
		}
		for (int i = 0; i < wordList.size(); i++) {
			for (int j = i + 1; j < wordList.size(); j++) {
				// 若i和j只差一个字符，则将其相连
				if (connect(wordList.get(i), wordList.get(j))) {
//					graph[wordList[i]].push_back(wordList[j]);
//					graph[wordList[j]].push_back(wordList[i]);
					graph.get(wordList.get(i)).add(wordList.get(j));
					graph.get(wordList.get(j)).add(wordList.get(i));
				}
			}
		}
	}

	public static class Pair {
		public String word;
		public int step;

		public Pair(String word, int step) {
			this.word = word;
			this.step = step;
		}
	}

	public static int BFS_graph(String beginWord, String endWord, Map<String, List<String>> graph) {
		// 搜索队列
//    queue<pair<string, int>>Q;
		Deque<Pair> queueNode = new ArrayDeque<Pair>();
		// 标记已访问节点
//    set<string>visit;
		Set<String> visit = new HashSet<>();
		// 添加其实节点，初始化访问步数为1
//    Q.push(make_pair(beginWord, 1));
		Pair root = new Pair(beginWord, 1);
		queueNode.addLast(root);

		// 将起始节点标记为已访问
		visit.add(beginWord);
		while (!queueNode.isEmpty()) {
			// 获取队头的字符串和步数
//        string node=Q.front().first;
//        int step=Q.front().second;
//        Q.pop();
			Pair frontNode = queueNode.pollFirst();
			String node = frontNode.word;
			int step = frontNode.step;

			// 访问到了终止节点，则宽搜过程结束
			if (node == endWord) {
				return step;
			}
			// 获取node的全部邻接点
//        const vector<string>&neighbors=graph[node];
//        for(auto i : neighbors){
//            //若该邻接点未被访问
//            if(visit.find(i)==visit.end()){
//                Q.push(make_pair(i, step+1));
//                visit.insert(i);
//            }
//        }

			List<String> neighbors = graph.get(node);
			for (int i = 0; i < neighbors.size(); i++) {
				if (!visit.contains(neighbors.get(i))) {
					Pair nodePair = new Pair(neighbors.get(i), step + 1);
					queueNode.addLast(nodePair);
					visit.add(neighbors.get(i));
				}
			}
		}
		return 0;
	}

	public static int ladderLength(String beginWord, String endWord, List<String> wordList) {
		if (wordList.isEmpty())
			return 0;
//		map<string, vector<string>> graph;
		Map<String, List<String>> graph = new HashMap<String, List<String>>();
		// 构造图
		construct_graph(beginWord, wordList, graph);
		return BFS_graph(beginWord, endWord, graph);
	}

	public static void main(String[] args) {
		String beginWord = "hit";
		String endWord = "cog";
		List<String> wordList = new ArrayList<String>();
//		{"hot","dot","dog","lot","log","cog"};
		wordList.add("hot");
		wordList.add("dot");
		wordList.add("dog");
		wordList.add("lot");
		wordList.add("log");
		wordList.add("cog");

		int count = ladderLength(beginWord, endWord, wordList);
		System.out.println(count);
	}
}
